package algorithm_demo.demo05;

/**
 * 动态规划总结
 *
 * @author Api
 * @date 2023/3/20 0:22
 */
public class Code12_CoinsWay {
    /*
     * 题目-->(找到)-->暴力递归等算法（尝试）找出重复解-->（可变参数（不讲究组织））
     * -->记忆化搜索-->(精细化组织)-->经典的动态规划
     * */

    public static int way1(int[] arr, int aim) {
        if (arr == null || arr.length == 0 || aim < 0) {
            return 0;
        }
        return process(arr, 0, aim);
    }

    //f(0..1000)
    //
    /*暴力递归*/
    public static int process(int[] arr, int index, int rest) {
//        if (rest < 0) {
//            return 0;
//        } //可以省掉 base case
        //rest>=0
        //没有货币可以选择了
        if (index == arr.length) {
            return rest == 0 ? 1 : 0;
        }
        //当前有货币，arr[index]
        int ways = 0;
        for (int zhang = 0; zhang * arr[index] <= rest; zhang++) {
            ways += process(arr, index + 1, rest - (zhang * arr[index]));
        }
        return ways;
    }

    public static int way2(int[] arr, int aim) {
        if (arr == null || arr.length == 0 || aim < 0) {
            return 0;
        }
        int N = arr.length;
        int[][] dp = new int[N + 1][aim + 1];
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[0].length; j++) {
                dp[i][j] = -1;
            }
        }
        return process2(arr, 0, aim, dp);
    }
    /*记忆化搜索*/

    //如果index和rest的参数组合，是没有算过的，dp[index][rest] == -1
    //如果index和rest的参数组合，是算过的，dp[index][rest] > -1
    public static int process2(int[] arr, int index, int rest, int[][] dp) {
        if (dp[index][rest] != -1){
            return dp[index][rest];
        }
        if (index == arr.length) {
            dp[index][rest] = rest == 0 ? 1 : 0;
            return dp[index][rest];
        }
        //当前有货币，arr[index]
        int ways = 0;
        for (int zhang = 0; zhang * arr[index] <= rest; zhang++) {
            ways += process(arr, index + 1, rest - (zhang * arr[index]));
        }
        dp[index][rest] = ways;
        return ways;
    }
    /*记忆化搜索*/
    public static int way3(int[] arr, int aim){
        if (arr == null || arr.length == 0 || aim < 0) {
            return 0;
        }
        int N = arr.length;
        int[][]dp = new int[N+1][aim+1];
        dp[N][0] = 1; //dp[N][1...aim] = 0
        //为什么倒着写for，原因是当前的值依赖的是下一次遍历的值，比如递归中
        //ways += process(arr, index + 1, rest - (zhang * arr[index]));
        for(int index = N-1; index >=0; index--){
            for(int rest = 0; rest<=aim;rest++){//从左往右遍历
                int ways = 0;
                for (int zhang = 0; zhang * arr[index] <= rest; zhang++) {
                    ways+=dp[index + 1][rest - (zhang * arr[index])];
                }
                dp[index][rest] = ways;
            }
        }
        return dp[0][aim];
    }

    /*经典动态规划*/
    public static int way4(int[] arr, int aim){
        if (arr == null || arr.length == 0 || aim < 0) {
            return 0;
        }
        int N = arr.length;
        int[][]dp = new int[N+1][aim+1];
        dp[N][0] = 1; //dp[N][1...aim] = 0
        //为什么倒着写for，原因是当前的值依赖的是下一次遍历的值，比如递归中
        //ways += process(arr, index + 1, rest - (zhang * arr[index]));
        for(int index = N-1; index >=0; index--){
            for(int rest = 0; rest<=aim;rest++){//从左往右遍历
                dp[index][rest] = dp[index+1][rest];
                if (rest - arr[index] >= 0){
                    dp[index][rest]+=dp[index][rest-arr[index]];
                }
            }
        }
        return dp[0][aim];
    }

    public static void main(String[] args) {
        int[] arr = {5,10,50,100};
        int sum = 1000;
        System.out.println(way1(arr, sum));
        System.out.println(way2(arr, sum));
        System.out.println(way3(arr, sum));
        System.out.println(way4(arr, sum));
    }
}
